package cn.cxq.learning.tree;

import org.junit.jupiter.api.Test;

/**
 * 剑指offer
 * 树的子结构
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：853686
 * 本题知识点： 二叉树 树
 *  算法知识视频讲解
 * 题目描述
 * 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
 * 示例1
 * 输入
 * {8,8,#,9,#,2,#,5},{8,9,#,2}
 * 返回值
 * true
 */
public class HasSubtree {

    boolean flag; // true表示找到了，false表示没找到

    @Test
    public void test() {
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(8);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(9);
        root.left.right = new TreeNode(2);
        root.left.right.left = new TreeNode(4);
        root.left.right.right = new TreeNode(7);

        TreeNode root2 = new TreeNode(8);
        root2.left = new TreeNode(8);
        root2.right = new TreeNode(8);

        boolean b = HasSubtree(root, root2);
        System.out.println(b);
    }

    // 思路：前序遍历root1树，从他的每一个节点开始与root2树遍历对照，如果有一个不相符的就使flag置为false。
    // 如果有一次是true的，证明某一个节点作为根的树是包含root2树结构的，结束函数，找到了。
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {

        if (root1 == null || root2 == null) {
            return false;
        }

        findSubtree(root1, root2);

        return flag;
    }

    // 遍历root1寻找子树
    private void findSubtree(TreeNode node, TreeNode root2) {

        if (node == null) {
            return;
        }

        flag = true;
        isSubtree(node, root2);
        if (flag) return; // 如果flag为true表示找到了，结束函数

        if (!flag) {
            findSubtree(node.left, root2);
        }
        if (!flag) {
            findSubtree(node.right, root2);
        }
    }

    // 判断树是否符合子树结构，只要有一个不符合要求就让flag置为false
    private void isSubtree(TreeNode node, TreeNode node2) {
        if (node2 == null) {
            return;
        }

        if (node == null) {
            flag = false;
        } else if (node.val != node2.val) {
            flag = false;
        }

        if (flag) {
            isSubtree(node.left, node2.left);
        }

        if (flag) {
            isSubtree(node.right, node2.right);
        }
    }
}
